﻿// Sequin.Sequences.Mining.SequenceMiner
//
// (c) 2011 Arthur Pitman
//
// Part of the Sequin Library
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License (Version 2.1) as published by the Free Software Foundation.
// 
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
// 
// You should have received a copy of the GNU Lesser General Public
// License (Version 2.1) along with this library; if not, write to the 
// Free Software Foundation, Inc., 
// 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
// or see <http://www.gnu.org/licenses/>.
	  
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;
using System.Threading;

namespace Sequin.Sequences.Mining
{
	/// <summary>
	/// Sequence miner based on the PrefixSpan algorithm (Pei et al.)
	/// Implements (primative) multithreading - this needs work!
	/// </summary>
	public class SequenceMiner : ISequenceMiner
	{
		/// <summary>
		/// Optional observer of mining events
		/// </summary>
		protected ISequenceMinerObserver sequenceMinerObserver = null;

		/// <summary>
		/// Maximum number of threads
		/// Actual number may be less due to the configuration of the <see cref="ThreadPool"/> class
		/// </summary>
		protected int maximumThreadCount = 0;

		/// <summary>
		/// Maximum depth at which forking can occur, i.e. new threads can be created
		/// 
		/// </summary>
		protected int maximumForkDepth = 0;

		/// <summary>
		/// Used to lock the thread count variable
		/// </summary>
		protected readonly object threadCountLock = new object();

		/// <summary>
		/// The current number of projections assigned to threads
		/// </summary>
		protected int threadCount = 0;
	
		/// <summary>
		/// Accumulates results of the current mining operation
		/// </summary>
		protected SequenceMinerResult result;

		/// <summary>
		/// Minimum support count of the current mining operation
		/// </summary>
		protected int minimumSupportCount;

		/// <summary>
		/// Used to lock the nextProjectionId variable
		/// </summary>
		protected readonly object nextProjectionIdLock = new object();

		/// <summary>
		/// Stores next id for projections
		/// </summary>
		protected int nextProjectionId = 0;

		/// <summary>
		/// System ticks when mining started
		/// </summary>
		protected int startTicks = 0;

		/// <summary>
		/// Maximum ticks allowed  for mining
		/// </summary>
		protected int maximumTime = 0;

		/// <summary>
		/// Initializes a new instance of the <see cref="SequenceMiner"/> class
		/// </summary>
		/// <param name="maximumThreadCount">Maximum number of threads</param>
		/// <param name="maximumForkDepth">Maximum depth at which forking can occur</param>
		/// <param name="sequenceMinerObserver">Optional observer of mining events</param>
		public SequenceMiner(int maximumThreadCount, int maximumForkDepth, ISequenceMinerObserver sequenceMinerObserver = null)
		{
			this.maximumThreadCount = maximumThreadCount;
			this.maximumForkDepth = maximumForkDepth;
			this.sequenceMinerObserver = sequenceMinerObserver;
		}

		/// <summary>
		/// Mines sequential patterns from the specified sequences
		/// This method is not thread safe: do not call this method on the same object from multiple threads
		/// </summary>
		/// <param name="sequences">The sequences to mine</param>
		/// <param name="minimumSupportCount">Minimum support count</param>
		/// <param name="maximumTime">Maximum time (milliseconds) to spend mining</param>
		/// <returns>The result of the mining operation</returns>
		public SequenceMinerResult Mine(IEnumerable<Sequence> sequences, int minimumSupportCount, int maximumTime)
		{			
			this.minimumSupportCount = minimumSupportCount;
			this.maximumTime = maximumTime;

			result = new SequenceMinerResult();

			if (sequenceMinerObserver != null)
				sequenceMinerObserver.OnStartMining();

			startTicks = Environment.TickCount;

			// reset projection ids, create an initial projection and begin mining
			nextProjectionId = 0;
			var initialProjection = CreateInitalProjection(sequences);

			// generate root projection
			if (sequenceMinerObserver != null)
				sequenceMinerObserver.OnGenerateProjection(initialProjection);

			ScheduleExpandProjection(initialProjection);

			// wait for all mining to complete
			lock (threadCountLock)
			{
				while (threadCount > 0)
				{
					Monitor.Wait(threadCountLock);
				}
			}

			result.TimeTaken = Environment.TickCount - startTicks;
			
			if (sequenceMinerObserver != null)
				sequenceMinerObserver.OnFinishMining();
			return result;
		}

		/// <summary>
		/// Creates an intial projection by filtering a set of sequences, removing items that don't satisfy the minimum support criterion
		/// </summary>
		/// <param name="inputSequences">The <see cref="Sequence"/> objects to filter</param>		
		/// <returns>The initial projection</returns>
		protected Projection CreateInitalProjection(IEnumerable<Sequence> inputSequences)
		{
			// deduce item frequencies
			var itemFrequencies = new Dictionary<int, int>();
			foreach (var sequence in inputSequences)
			{
				var itemsInSequence = new HashSet<int>();
				foreach (var element in sequence.Value)
				{
					foreach (var itemId in element)
					{
						if (!itemsInSequence.Contains(itemId))
						{
							if (itemFrequencies.ContainsKey(itemId))
								itemFrequencies[itemId]++;
							else
								itemFrequencies.Add(itemId, 1);
							itemsInSequence.Add(itemId);
						}
					}
				}
			}

			var frequentItems = new HashSet<int>(from x in itemFrequencies
												 where x.Value >= minimumSupportCount
												 select x.Key);

			// purge and create intial projection
			var projectedSequences = new List<ProjectedSequence>();
			foreach (var sequence in inputSequences)
			{
				var rawSequence = new List<int[]>();
				foreach (var element in sequence.Value)
				{
					var newElement = new List<int>();
					foreach (var item in element)
					{
						if (frequentItems.Contains(item))
							newElement.Add(item);
					}
					if (newElement.Count > 0)
						rawSequence.Add(newElement.ToArray());
				}
				if (rawSequence.Count > 0)
					projectedSequences.Add(new ProjectedSequence(new Sequence(rawSequence.ToArray()), -1));
			}

			return new Projection(GetNextProjectionId(), projectedSequences);
		}

		/// <summary>
		/// Gets the next projection id
		/// </summary>
		/// <returns>The next projection id</returns>
		protected int GetNextProjectionId()
		{
			lock (nextProjectionIdLock)
			{
				var x = nextProjectionId;
				nextProjectionId++;
				return x;
			}
		}

		/// <summary>
		/// Schedules a projection for expansion, either by the calling thread or a new thread
		/// </summary>
		/// <param name="projection">The projection to expand</param>
		protected void ScheduleExpandProjection(Projection projection)
		{
			// detemine threading
			bool createThread = false;
			if (projection.Depth <= maximumForkDepth)
			{
				lock (threadCountLock)
				{
					if (threadCount < maximumThreadCount)
					{
						threadCount++;
						createThread = true;
					}
				}
			}

			// create a new thread or use current one
			if (createThread)
				ThreadPool.QueueUserWorkItem(ExpandProjectionCallBack, projection);
			else
				ExpandProjection(projection);
		}

		/// <summary>
		/// Call back for expanding a projection with a new thread
		/// </summary>
		/// <param name="state">Holds the projection to expand</param>
		protected void ExpandProjectionCallBack(Object state)
		{
			var currentProjection = (Projection)state;
			ExpandProjection(currentProjection);
			lock (threadCountLock)
			{
				threadCount--;
				Monitor.Pulse(threadCountLock);
			}
		}

		/// <summary>
		/// Expands the specified projection generating child projections
		/// This is main recursive method of the sequence miner
		/// </summary>
		/// <param name="projection">The projection to expand</param>
		protected virtual void ExpandProjection(Projection projection)
		{
			int timeTaken = Environment.TickCount - startTicks;

			lock (result)
			{
				if (result.Aborted)
					return;

				if (timeTaken > maximumTime)
				{
					result.Aborted = true;
					return;
				}
				result.ProjectionsExpanded++;
			}

			if (sequenceMinerObserver != null)
				sequenceMinerObserver.OnExpandProjection(projection);

			// get last element of prefix, needed for extension testing
			int[] lastPrefixElement = null;
			int lastItemInLastElement = -1;
			if (projection.ProjectingSequence.Value.Length > 0)
			{
				lastPrefixElement = projection.ProjectingSequence.Value[projection.ProjectingSequence.Value.Length - 1];
				lastItemInLastElement = lastPrefixElement[lastPrefixElement.Length - 1];
			}

			// calculate local frequent items            
			var iExtensionProjectionBases = new Dictionary<int, List<ProjectedSequence>>();
			var sExtensionProjectionBases = new Dictionary<int, List<ProjectedSequence>>();

			var uniqueItemsExtensions = new HashSet<int>();
			var uniqueItems = new HashSet<int>();

			foreach (var projectedSequence in projection.ProjectedDb)
			{
				var sequence = projectedSequence.Seq;
				var rawSequence = sequence.Value;

				uniqueItemsExtensions.Clear();
				var firstPoint = projectedSequence.ProjectionIndex;
				if (firstPoint != -1)
				{
					var element = rawSequence[firstPoint];

					foreach (var item in element)
					{
						if (item <= lastItemInLastElement)
							continue;

						if (!uniqueItemsExtensions.Contains(item))
						{
							uniqueItemsExtensions.Add(item);
							List<ProjectedSequence> db = null;
							if (!iExtensionProjectionBases.TryGetValue(item, out db))
								iExtensionProjectionBases.Add(item, db = new List<ProjectedSequence>());
							var ps = new ProjectedSequence(projectedSequence.Seq, firstPoint);
							db.Add(ps);
						}
					}
				}

				uniqueItems.Clear();
				for (int i = firstPoint + 1; i < rawSequence.Length; i++)
				{
					var element = rawSequence[i];

					// check if the element contains the last element of prefix
					if ((lastPrefixElement != null) && Sequence.ElementContains(element, lastPrefixElement))
					{
						foreach (var item in element)
						{
							if (item <= lastItemInLastElement)
								continue;
							if (!uniqueItemsExtensions.Contains(item))
							{
								uniqueItemsExtensions.Add(item);
								List<ProjectedSequence> db = null;
								if (!iExtensionProjectionBases.TryGetValue(item, out db))
									iExtensionProjectionBases.Add(item, db = new List<ProjectedSequence>());
								var ps = new ProjectedSequence(projectedSequence.Seq, i);
								db.Add(ps);
							}
						}
					}

					foreach (var item in element)
					{
						if (!uniqueItems.Contains(item))
						{
							uniqueItems.Add(item);
							List<ProjectedSequence> db = null;
							if (!sExtensionProjectionBases.TryGetValue(item, out db))
								sExtensionProjectionBases.Add(item, db = new List<ProjectedSequence>());
							var ps = new ProjectedSequence(projectedSequence.Seq, i);
							db.Add(ps);
						}
					}
				}
			}

			var validIExtensionProjections = (from x in iExtensionProjectionBases
												where x.Value.Count >= minimumSupportCount
												select new Projection(GetNextProjectionId(),
													projection,
													projection.ProjectingSequence.ApplyIExtension(x.Key), 
													x.Value));

			var validSExtensionProjections = (from x in sExtensionProjectionBases
												where x.Value.Count >= minimumSupportCount
												select new Projection(GetNextProjectionId(), 
													projection, 
													projection.ProjectingSequence.ApplySExtension(x.Key),
													x.Value));

			if (ShouldEmitPattern(projection, validIExtensionProjections, validSExtensionProjections))
			{
				if (sequenceMinerObserver != null)
					sequenceMinerObserver.OnEmitPattern(projection);
				lock (result.Patterns)
				{
					result.Patterns.Add(new SequentialPattern(projection.ProjectingSequence, projection.ProjectedDb.Count));
					result.PatternsEmitted++;
				}
			}			
			
			// follow extensions
			foreach (var childProjection in validIExtensionProjections.Union(validSExtensionProjections))
			{
				if (sequenceMinerObserver != null)
					sequenceMinerObserver.OnGenerateProjection(childProjection);
				lock (result)
				{
					result.ProjectionsGenerated++;
				}
				if (ShouldExpandProjection(childProjection))
					ScheduleExpandProjection(childProjection);
			}
		}

		/// <summary>
		/// Decides if a projection should be expanded
		/// Override this method to implement pruning
		/// </summary>
		/// <param name="projection">The projection to consider</param>
		/// <returns><c>true</c> if the projection should be expanded</returns>
		protected virtual bool ShouldExpandProjection(Projection projection)
		{
			return true;
		}

		/// <summary>
		/// Decides if a sequential pattern should be emitted for the projection
		/// Override this method to mine a specific subset of patterns
		/// </summary>
		/// <param name="projection">The projection to consider</param>
		/// <param name="validIExtensionProjections">Item extensions</param>
		/// <param name="validSExtensionProjections">Sequence extensions</param>
		/// <returns><c>true</c> if a sequential pattern should be emitted</returns>
		protected virtual bool ShouldEmitPattern(Projection projection, IEnumerable<Projection> validIExtensionProjections, IEnumerable<Projection> validSExtensionProjections)
		{
			return true;
		}
	}
}